package com.example.leetcode.trainingcamp.week7.Thursday;

/**
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 */
public class Test105 {


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return myBuildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    public TreeNode myBuildTree(int[] preorder,int i,int j,int[] inorder,int l,int k){
        if (i>j) return null;
        TreeNode root = new TreeNode(preorder[i]);
        int s = l;
        while (s<=k && preorder[i] != inorder[s]){
            s++;
        }
        int size = s - l;
        TreeNode left = myBuildTree(preorder,i+1,i+size,inorder,l,s-1);
        TreeNode right = myBuildTree(preorder,i+size+1,j,inorder,s+1,k);
        root.left = left;
        root.right = right;
        return root;
    }
}
